1. Field of the Invention
The present invention relates to a technique of encoding and decoding an image.
2. Description of the Related Art
One of generally known compression encoding techniques is JPEG. JPEG divides image data to be encoded into blocks each made up of a plurality of pixels, and performs DCT, quantization, and entropy coding for each block. In the series of processes, a quantization step value used in the quantization process is particularly an important parameter which determines the amount of code. When the quantization step value is set large, the DCT coefficient value becomes 0 or almost 0, increasing the compression ratio. The larger the quantization step value becomes, the larger the difference from an original image before encoding becomes. This appears as degradation of the image quality.
As a technique of increasing the coding efficiency while preventing degradation of the image quality, Japanese Patent Laid-Open No. 10-257494 (to be referred to as reference 1 hereinafter) is known. According to reference 1, an input image is divided into blocks. The code amount of a block encoded without performing difference prediction is compared with that of a block encoded after performing difference prediction. A method exhibiting a smaller amount of code is selected for each block.
However, if an image is encoded at an excessively high compression ratio according to a lossy encoding method, many pieces of image information are omitted, and degradation of the image quality stands out. The above-mentioned conventional encoding method still has room for improvement in terms of reducing the amount of code while maintaining the image quality to some degree.
An attempt has conventionally been made to divide an image into an image (to be referred to as a character-line image hereinafter) such as a character or a line draw image requiring high resolution, and an image (to be referred to as a halftone image hereinafter) such as a photographic image or background, compress these images by different compression methods, and concatenate these data after compression, thereby generating encoded data of a fixed length. As for a character-line image, binary identification information for identifying whether each pixel forms the character-line image, and the pixel value are losslessly encoded with a variable length. To the contrary, a halftone image is lossily encoded to fall within the remaining code amount of a fixed length. To ensure the image quality in fixed length coding, it is considered to be the most important to efficiently perform variable length coding of binary identification information for all patterns, that is, improve the worst value of the compression efficiency.
Conventional methods of compressing binary data are generally MH (Modified Huffman), MR (Modified READ), and MMR (Modified MR) standardized by G3 facsimile of ITU-TS. These methods are compression algorithms based on run length coding. For example, MH is a method of encoding a run length in the raster direction by a predetermined code word.
As a technique of compressing a binary image block, Japanese Patent No. 2936042 (to be referred to as reference 2 hereinafter) is proposed. Reference 2 discloses a technique of dividing a binary image into blocks of 4×4 to 16×16 pixels, replacing each block size with a code, and for the 4×4 size, encoding pixel pattern information in the block of an original image. For other sizes, reference 2 discloses a technique of compositing block tone information codes each obtained by counting the number of black pixels in a block, thereby compressing an image.
These compression methods can efficiently compress simple images with high continuity, like a character or line image, but are not suitable for more complicated images. For example, when PC application software creates a document using a halftone image or semitransparent image and the PC renders the document, patterns as shown in FIGS. 14A and 14B often appear. As is apparent from FIGS. 14A and 14B, a halftone or semitransparent portion is not always expressed by a pixel of a halftone density value, and the density is expressed at a ratio at which pixels of high and low density values appear. An image having many density change points, like ones shown in FIGS. 14A and 14B, cannot ensure a long run length. In many cases, compression algorithms such as MH and MR are not suited to such an image.
In reference 2, the algorithm assures only the density for blocks having sizes other than the 4×4 size, and cannot assure the shapes of the blocks. The shape undesirably changes after decoding.